1. Field of the Invention
Methods consistent with the present invention relate to updating a check node in a low density parity check (LDPC) decoder and, more particularly, to a method for approximating a check node update rule to a sum of exponential functions. The method of the present invention lowers complexity of the check node update process and is comparable in performance to that of a belief propagation (BP) algorithm in digital communication systems that transmit high-speed data in order to update a check node in an LDPC decoder using the BP algorithm.
2. Description of the Related Art
In general, a low density parity check (LDPC) code is defined by a parity check matrix having a very small number of “1s” in each row and in each column as shown in FIG. 1A, and the LDPC code can be represented by a “factor graph,” which includes check nodes, variable nodes and edges.
An LDPC code can be decoded using a belief propagation (BP) algorithm, which enables accurate and complete parallel decoding of even very long codewords. Accordingly, the processing speed of the BP algorithm can be high. An LDPC decoder based on a BP algorithm is a soft decision decoder which is based on likelihood from channel output, and the BP algorithm shows a higher performance than a bounded distance decoder. Because an LDPC with the BP algorithm is a good decoder, LDPC codes with large block sizes are practical for implementation. LDPC codes with large block sizes are advantageous because they show a capability to approach the Shannon-limit and have a large minimum distance. Thus, the detection error, which appears in turbo codes with small minimum distances, hardly shows in the LDPC codes with large block sizes.
For LDPC codes, a parity check matrix H provides the structure for the decoding algorithm. As shown in FIG. 1A, there is an edge in the graph connecting the variable and check nodes exactly when there is a “1” in the matrix H. Accordingly, an association can be made between edge and the non-zero entries of the matrix H. This graph, which is called a “factor graph,” completely describes all the relations of the codes and can be used for decoding by using a BP algorithm. Starting with the input consisting of messages for the variable nodes, the BP algorithm uses the parity-check relationships among the bits in order to iteratively update and pass messages between the variable nodes and check nodes. Two steps, one updating of all the check nodes and one updating of all the variable nodes, comprise a single iteration. With a binary communication system, a message is expressed using a log-likelihood ratio (LLR) as in Equation 1:
                              LLR          ⁡                      (            x            )                          =                  log          ⁢                                    P              ⁡                              (                                  x                  =                  1                                )                                                    P              ⁡                              (                                  x                  =                  0                                )                                                                        (        1        )            
In this case, because the variable node update rule is formed using an algorithm with only summing operations. Thus, the values can be easily realized. However, the check node update rule includes a hyperbolic tangent function and many multiplication operations. Accordingly, the BP algorithm used in the check node update rule is a Sum-Product algorithm and the values cannot be easily realized.
FIG. 1B describes the process of updating a message, LLR(λci→vj), from a check node Ci to a variable node Vj. If dc represents the number of variable nodes, LLR(λci→vj) is updated by the rule expressed in Equation 2 using messages from (dc−1) variable nodes V0, V1, ˜Vdc−2, and Vdc−1 (except Vi) connected to a check node Ci.
                              LLR          ⁡                      (                          λ                                                c                  i                                →                                  v                  j                                                      )                          =                                                            (                                  -                  1                                )                                            d                c                                      ·            2                    ⁢                                          ⁢                                    tanh                              -                1                                      (                                          ∏                                                      j                    ′                                    ∈                                                            N                      ⁡                                              (                                                  c                          i                                                )                                                              ⁢                    \                    ⁢                    j                                                              ⁢                              tanh                ⁡                                  (                                                            1                      2                                        ⁢                                          (                                              LLRλ                                                                              v                            j                                                    →                                                      c                            i                                                                                              )                                                        )                                                      )                                              (        2        )            
As shown in FIG. 1B, messages on the edges from a check node Ci to each of the dc variable nodes V0, V1, ˜Vdc−2 must be updated. Thus, Equation 2 is executed dc times for each check node, which means that dc×(dc−1) operations are required for one check node.
Alternatively, the messages on the edges from a check node Ci to each of the dc variable nodes V0, V1, ˜Vdc−2 may be updated by decomposing the messages into dc messages for each check node as shown in FIG. 1C. The messages are updated by executing the function shown in Equation 3. The method in FIG. 1C requires a smaller number of operations than the method in FIG. 1B.
                                                                        LLR                ⁡                                  (                                      λ                                                                  c                        i                                            =                                              >                                                  v                          j                                                                                                      )                                            =                            ⁢                                                                    (                                          -                      1                                        )                                                        d                    c                                                  ·                                  L                  ⁡                                      (                                                                  f                                                  j                          -                          1                                                                    +                                              b                                                  j                          +                          1                                                                                      )                                                                                                                          =                            ⁢                                                                    (                                          -                      1                                        )                                                        d                    c                                                  ·                                  [                                      log                    ⁢                                                                  1                        +                                                  ⅇ                                                      L                            ⁢                                                          (                                                                                                f                                                                      j                                    +                                    1                                                                                                  +                                                                  b                                                                      j                                    +                                    1                                                                                                                              )                                                                                                                                                                            ⅇ                                                      L                            ⁢                                                          (                                                              f                                                                  j                                  -                                  1                                                                                            )                                                                                                      +                                                  ⅇ                                                      L                            ⁢                                                          (                                                              b                                                                  j                                  +                                  1                                                                                            )                                                                                                                                                            ]                                                                                                        =                            ⁢                                                                    (                                          -                      1                                        )                                                        d                    c                                                  ·                                  [                                      sign                    ⁢                                                                                  [                                          L                      ⁢                                                                        (                                                      f                                                          j                              -                              1                                                                                )                                                ·                        sign                                            ⁢                                                                                          ⁢                                              (                                                                              L                            ⁡                                                          (                                                              b                                                                  j                                  +                                  1                                                                                            )                                                                                ·                                                                                                                                                                                                          ⁢                              min                ⁡                                  (                                                                                                          L                        ⁡                                                  (                                                      f                                                          j                              -                              1                                                                                )                                                                                                            ,                                                                                        L                        ⁡                                                  (                                                      b                                                          j                              +                              1                                                                                )                                                                                                                            )                                                                                                                                        ⁢                                                                            -                                              g                        ⁡                                                  (                                                                                    L                              ⁡                                                              (                                                                  f                                                                      j                                    -                                    1                                                                                                  )                                                                                      ·                                                          L                              ⁡                                                              (                                                                  b                                                                      j                                    +                                    1                                                                                                  )                                                                                                              )                                                                                                            (                      A                      )                                                        +                                                            g                      ⁡                                              (                                                                              L                            ⁡                                                          (                                                              f                                                                  j                                  -                                  1                                                                                            )                                                                                ·                                                      L                            ⁡                                                          (                                                              b                                                                  j                                  +                                  1                                                                                            )                                                                                                      )                                                                                    (                      B                      )                                                                      ]                            .                                                          (        3        )            
An update value of each edge message for the check node shown in FIG. 1C can be expressed with Sign-Min function and a function g(x) shown in (A) and (B) of Equation 3. Here, the function (g)x may be expressed as in Equation 4:g(x)=log(1+e−|x|)  (4)
Although the check node updating method of FIG. 1C using Equation 3 requires a smaller number of operations than the BP algorithm, it still includes the function g(x) that is difficult to implement.
Thus, several methods for easily implementing the function g(x) have been proposed. The Sign-Min method assumes g(x)=0 and takes only sign and minimum values of two input values to compute Equation 3 easily. The Normalize-BP algorithm sets g(x) to some constant value that is larger than “1” to revise the Sign-Min method. However, these methods have poor performance when compared to the existing BP algorithm.
The quantization method, linear approximation method, piecewise linear approximation method, and the like are examples of methods of approximating g(x) to g′(x) in order to easily realize g(x). The piecewise linear approximation method has a higher performance than existing methods and thus, shows a performance similar to that of the BP algorithm. However, the piecewise linear approximation method uses different functions at different intervals and requires a look-up table.